package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

public class TopKFrequent {

	public List<Integer> topKFrequent(int[] nums, int k) {
		List<Integer> list = new ArrayList<Integer>();
		int[] m;
		HashMap<Integer, Integer> map = new HashMap<>();

		if (nums == null || nums.length <= 0) {
			return list;
		}
		Integer count = 0;
		for (int i = 0; i < nums.length; i++) {
			if ((count = map.get(nums[i])) != null) {
				map.put(nums[i], count + 1);
			} else {
				map.put(nums[i], 1);
			}
		}
		// and then we sort the map
		List<Entry<Integer, Integer>> set = new ArrayList<>(map.entrySet());
		Collections.sort(set, new Comparator<Entry<Integer, Integer>>() {
			@Override
			public int compare(Entry<Integer, Integer> o1,
					Entry<Integer, Integer> o2) {
				// 按照从大到小的顺序排
				return o2.getValue() - o1.getValue();
			}
		});
		for (int i = 0; i < k; i++) {
			list.add(set.get(i).getKey());
		}
		return list;
	}
}
